# 给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。
#
#  示例:
#
#
# 输入: [4, 6, 7, 7]
# 输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7
# ]]
#
#  说明:
#
#
#  给定数组的长度不会超过15。
#  数组中的整数范围是 [-100,100]。
#  给定数组中可能包含重复数字，相等的数字应该被视为递增的一种情况。
#
#  Related Topics 深度优先搜索
#  👍 185 👎 0


# TODO 强烈建议弄懂去重原理 ，对于排列类型题目的去重非常有帮助
# todo 去重问题
# leetcode submit region begin(Prohibit modification and deletion)
import sys
from typing import List


class Solution:

    def __init__(self):
        self.tmp = []
        self.res = []

    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        if not nums or len(nums) == 0:
            return []

        # def dfs1(nums, dep, last, n, tmp, res):
        #     if dep >= n:
        #         return
        #
        #     num = nums[dep]
        #     # 在空序列的情况下，要确定打头的数字必须是第一次出现，
        #     # 这是为了避免 1,3,3,3 这种情况下 取 第 1,2 位置上的 3,3 序列会和 2,3 位置上的 3,3 序列重复
        #
        #     if len(tmp) == 0:
        #         if is_first(nums, dep):
        #             tmp.append(num)
        #             dfs1(nums, dep + 1, dep, n, tmp, res)
        #             tmp.pop()
        #             dfs1(nums, dep + 1, last, n, tmp, res)
        #     else:
        #         if tmp[len(tmp) - 1] <= num and is_first_since_last_added(nums, dep, last):
        #             tmp.append(num)
        #
        #             if len(tmp) >= 2:
        #                 print(dep, last, tmp[:])
        #                 res.append(tmp[:])
        #
        #             dfs1(nums, dep + 1, dep, n, tmp, res)
        #             tmp.pop()
        #             dfs1(nums, dep + 1, last, n, tmp, res)
        #
        # # 去重写法
        # # 如果在上次添加的数字和当前要加的数字之间有数字和当前数字相同，那么这种序列是不被允许的，会导致重复
        # def is_first_since_last_added(nums, curr, last) -> bool:
        #     for i in range(last + 1, curr):
        #         if nums[i] == nums[curr]:
        #             return False
        #
        #     return True
        #
        # # 针对空的情况
        # def is_first(nums, curr):
        #     for i in range(0, len(nums)):
        #         if nums[i] == nums[curr]:
        #             return i == curr
        #
        #     return True
        #
        # res = []
        #
        # tmp = []

        def dfs(curr, last, nums):
            if curr == len(nums):
                if len(self.tmp) >= 2:
                    self.res.append(self.tmp[:])

                return

            if nums[curr] >= last:
                self.tmp.append(nums[curr])
                dfs(curr + 1, nums[curr], nums)
                self.tmp.pop()

            if nums[curr] != last:
                dfs(curr + 1, last, nums)

        dfs(0, -sys.maxsize - 1, nums)

        """
        [1,2,2]
        对于两个相同的元素nums[i],nums[i+1],假设nums[i]与前面的元素last不相同，
        那么递归到第i个元素的时候，因为和前面一个元素不相同，
        所以会进行选择第i个元素与不选择i元素的递归。然后再考虑如果选择了第i个元素继续递归，
        cur>=last成立，可以也选择i+1元素继续递归。
        但是此时cur=last，所以不会有不选择i+1元素的递归了。
        再看没有选择第i个元素的，那么本次递归的last应该和前一次递归的last相同，
        自然选择与不选择的递归都会进行。每次的判断都是当前的数与上一个选择的数last相比较，
        所以这样的分析也会对不相邻的两个相同元素生效，只要相同元素被连续选择道理就都一样。
        """

        return self.res

    """
    利用 set 去重
    """

    def findSubsequences1(self, nums):
        # 定义了一个 set ，只加入一个空序列（可以理解成一粒种子，后面根据它会生出很多序列）
        subs = {()}
        for num in nums:
            tmp = {sub + (num,)
                   for sub in subs
                   if not sub or sub[-1] <= num}
            print(tmp)
            subs |= tmp
            print(subs)
        return [sub for sub in subs if len(sub) >= 2]


# leetcode submit region end(Prohibit modification and deletion)

print(Solution().findSubsequences1([1, 2, 2, 2]))

ex = {(1, 2), (1, 2)}

# ex |= ex
#
# print(type(ex))

print(ex)
